{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Combination Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: combinationSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #组合总和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>无重复元素</strong> 的整数数组&nbsp;<code>candidates</code> 和一个目标整数&nbsp;<code>target</code>&nbsp;，找出&nbsp;<code>candidates</code>&nbsp;中可以使数字和为目标数&nbsp;<code>target</code> 的 所有<em>&nbsp;</em><strong>不同组合</strong> ，并以列表形式返回。你可以按 <strong>任意顺序</strong> 返回这些组合。</p>\n",
    "\n",
    "<p><code>candidates</code> 中的 <strong>同一个</strong> 数字可以 <strong>无限制重复被选取</strong> 。如果至少一个数字的被选数量不同，则两种组合是不同的。&nbsp;</p>\n",
    "\n",
    "<p>对于给定的输入，保证和为&nbsp;<code>target</code> 的不同组合数少于 <code>150</code> 个。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>candidates = <code>[2,3,6,7], </code>target = <code>7</code>\n",
    "<strong>输出：</strong>[[2,2,3],[7]]\n",
    "<strong>解释：</strong>\n",
    "2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。\n",
    "7 也是一个候选， 7 = 7 。\n",
    "仅有这两种组合。</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>candidates = [2,3,5]<code>, </code>target = 8\n",
    "<strong>输出: </strong>[[2,2,2,2],[2,3,3],[3,5]]</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>candidates = <code>[2], </code>target = 1\n",
    "<strong>输出: </strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= candidates.length &lt;= 30</code></li>\n",
    "\t<li><code>2 &lt;= candidates[i] &lt;= 40</code></li>\n",
    "\t<li><code>candidates</code> 的所有元素 <strong>互不相同</strong></li>\n",
    "\t<li><code>1 &lt;= target &lt;= 40</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [combination-sum](https://leetcode.cn/problems/combination-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [combination-sum](https://leetcode.cn/problems/combination-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,6,7]\\n7', '[2,3,5]\\n8', '[2]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        results = []\n",
    "        def backtrack(remain, comb, next_start):\n",
    "            if remain == 0 and len(comb) == k:\n",
    "                results.append(list(comb))\n",
    "                return\n",
    "            elif remain < 0 or len(comb) == k:\n",
    "                return\n",
    "            for i in range(next_start, 9):\n",
    "                comb.append(i + 1)\n",
    "                backtrack(remain-i-1, comb, i + 1)\n",
    "                comb.pop()\n",
    "        backtrack(n, [], 0)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k, n):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        ans = []\n",
    "        \n",
    "        def dfs(combination, target, pose):\n",
    "            if target == 0 or len(combination) == k:\n",
    "                if target == 0 and len(combination) == k:\n",
    "                    ans.append(combination)\n",
    "                else:\n",
    "                    return\n",
    "            \n",
    "            for i in range(pose, 10):\n",
    "                if i > target:\n",
    "                    break\n",
    "                dfs(combination+[i], target-i, i+1)\n",
    "        dfs([], n, 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k, n):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def bt(res, cur, s, k, n):\n",
    "            if len(cur) > k:\n",
    "                return\n",
    "            elif len(cur) == k:\n",
    "                if s == n:\n",
    "                    res.append(cur[:])\n",
    "            else:\n",
    "                a = 1\n",
    "                if cur:\n",
    "                    a = cur[-1] + 1\n",
    "                while a < 10:\n",
    "                    cur.append(a)\n",
    "                    bt(res, cur, s + a, k, n)\n",
    "                    cur.pop()\n",
    "                    a += 1\n",
    "        res = []\n",
    "        bt(res, [], 0, k, n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k, n):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        a=[]\n",
    "        def add(start,count,sums,nums):\n",
    "            if count>k or sums>n:\n",
    "                return\n",
    "            if count==k and sums==n:\n",
    "                a.append(nums)\n",
    "            for i in range(start+1,10):\n",
    "                add(i,count+1,sums+i,nums+[i])\n",
    "        add(0,0,0,[])\n",
    "        return a\n",
    "        '''\n",
    "        a=[]\n",
    "        for i in range(1,8):\n",
    "            if not n-i>=18:\n",
    "                for j in range(i+1,8):\n",
    "                    if not n-i-j>=9:\n",
    "                        if n-i-j<=9 and n-i-j>j:\n",
    "                            a.append([i,j,n-i-j])\n",
    "                        else:\n",
    "                            break\n",
    "                    else:\n",
    "                        break\n",
    "            else:\n",
    "                break\n",
    "        return a\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def DFS(self, res, tmp, nums, k, n, w, su):\n",
    "        if su==n and k==len(tmp):\n",
    "            res.append(tmp.copy())\n",
    "            return\n",
    "        elif su>n or len(tmp)>k:\n",
    "            return\n",
    "        for i in range(w,len(nums)):\n",
    "            su+=nums[i]\n",
    "            tmp.append(nums[i])\n",
    "            self.DFS(res,tmp,nums,k,n,i+1,su)\n",
    "            del tmp[-1]\n",
    "            su-=nums[i]\n",
    "\n",
    "    def combinationSum3(self, k, n):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        res=[]\n",
    "        tmp=[]\n",
    "        su=0\n",
    "        nums=[1,2,3,4,5,6,7,8,9]\n",
    "        self.DFS(res,tmp,nums,k,n,0,su)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k, n):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        rl = []\n",
    "        self.func(0,[],0,0,rl,k,n)\n",
    "        return rl\n",
    "    def func(self,start,num,su,count,rl,k,n):\n",
    "        if count > k or su > n:\n",
    "            return\n",
    "        if count == k and su == n:\n",
    "            rl.append(num)\n",
    "            return\n",
    "        elif (count == k and su < n) or (count < k and su == n):\n",
    "            return\n",
    "        for i in range(start+1,10):\n",
    "           # print(num)\n",
    "            self.func(i,num+[i],su+i,count+1,rl,k,n)\n",
    "        \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k, n):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        self.result = []\n",
    "        self.path = [0 for i in range(10)]\n",
    "        self.lens = 0\n",
    "        self.dfs(1, k, n)\n",
    "        return self.result\n",
    "        \n",
    "    def dfs(self, idx, k, target):\n",
    "        if target == 0 and k == 0:\n",
    "            temp = []\n",
    "            for i in range(self.lens):\n",
    "                temp.append(self.path[i])\n",
    "            self.result.append(temp)\n",
    "            return\n",
    "            \n",
    "        elif target < 0  or idx >= 10:\n",
    "            return\n",
    "        \n",
    "        # use\n",
    "        self.path[self.lens] = idx\n",
    "        self.lens += 1\n",
    "        self.dfs(idx + 1, k - 1, target - idx)\n",
    "        self.lens -= 1\n",
    "        \n",
    "        # not use\n",
    "        self.dfs(idx + 1, k, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def combinationSum3(self, k, n):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        data = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "        return self.combinationSum(k, n, data)\n",
    "\n",
    "    def combinationSum(self, k, n, data):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :type n: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        if k == 1:\n",
    "            if n in data:\n",
    "                result.append([n])\n",
    "        else:\n",
    "            for i, j in enumerate(data):\n",
    "                temp = self.combinationSum(k - 1, n - j, data[i + 1:])\n",
    "                for t in temp:\n",
    "                    result.append([j] + t)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        nums=[1,2,3,4,5,6,7,8,9]\n",
    "        ans=[]\n",
    "        def helper(n,pre,last):\n",
    "            p=sum(pre)\n",
    "            if p==n and len(pre)==k:\n",
    "                ans.append(pre)\n",
    "                return\n",
    "            if p>n:\n",
    "                return \n",
    "            for i in range(last+1,10):\n",
    "                helper(n,pre+[i],i)\n",
    "        helper(n,[],0)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        if k<=0 or k>9 or n<=0 or n>45:\n",
    "            return []\n",
    "        res = []\n",
    "\n",
    "        def backTrack(m, cnt, total, tmp):\n",
    "            if cnt>k:\n",
    "                return\n",
    "            if cnt==k and total == n:\n",
    "                res.append(tmp)\n",
    "                return\n",
    "            for i in range(m, 10):\n",
    "                backTrack(i+1, cnt+1, total+i, tmp+[i])\n",
    "            \n",
    "        backTrack(1, 0, 0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        def backtrack(temp, K, summary, num):\n",
    "            if summary < 0:\n",
    "                return\n",
    "            if K == 0 and summary == 0:\n",
    "                res.append(temp)\n",
    "            if K == 0 and summary > 0:\n",
    "                return\n",
    "            for i in range(num, 0, -1):\n",
    "                backtrack(temp+[i], K-1, summary-i, i-1)\n",
    "        res = []\n",
    "        backtrack([], k, n, 9)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,pre_num,tmp_list,left_num,cur_num):\n",
    "        if pre_num == self.target and cur_num == self.target_num:\n",
    "            if sorted(list(tmp_list)) not in self.ans:\n",
    "                self.ans.append(sorted(list(tmp_list)))\n",
    "            return\n",
    "        if cur_num >= self.target_num:\n",
    "            return\n",
    "        if pre_num > self.target:\n",
    "            return\n",
    "        left_num_tmp = [i for i in left_num]\n",
    "        for num_tmp in left_num_tmp:\n",
    "            tmp_list.add(num_tmp)\n",
    "            left_num.remove(num_tmp)\n",
    "            self.dfs(pre_num+num_tmp,tmp_list,left_num,cur_num+1)\n",
    "            tmp_list.remove(num_tmp)\n",
    "            left_num.append(num_tmp)\n",
    "\n",
    "\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        self.target = n\n",
    "        self.target_num = k\n",
    "        self.ans = []\n",
    "        left_num = [1,2,3,4,5,6,7,8,9]\n",
    "        tmp_list = set()\n",
    "        self.dfs(0,tmp_list, left_num, 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        val = [i+1 for i in range(9)]\n",
    "        res = []\n",
    "        def backtrack(tmp, total, idx, num):\n",
    "            if total == n and num == k:\n",
    "                res.append(tmp)\n",
    "                return \n",
    "            for i in range(idx, 9):\n",
    "                if total + val[i] > n: continue\n",
    "                backtrack(tmp+[val[i]], total+val[i], i+1, num+1)\n",
    "        backtrack([], 0, 0, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        candidates = list(range(1,10))\n",
    "        res = []\n",
    "        def backtrack(i, temp_sum, temp_list):\n",
    "            if temp_sum==n and len(temp_list)==k:\n",
    "                res.append(temp_list)\n",
    "                return\n",
    "            \n",
    "            if len(temp_list)==k:\n",
    "                return\n",
    "\n",
    "            for j in range(i, len(candidates)):\n",
    "                if len(temp_list)==k-1:\n",
    "                    if temp_sum+candidates[j]>n or temp_sum+candidates[-1]<n: # 稍微优化了一下\n",
    "                        break\n",
    "                backtrack(j+1, temp_sum+candidates[j], temp_list+[candidates[j]])\n",
    "        backtrack(0,0,[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        self.combination(k, n, 1, [])\n",
    "        return self.res\n",
    "\n",
    "    def combination(self, k, target, start, res):\n",
    "        if len(res) == k and target == 0:\n",
    "            self.res.append(res)\n",
    "            return\n",
    "            \n",
    "        for i in range(start, 10):\n",
    "            self.combination(k, target-i, i+1, res+[i]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        self.combination(k, n, 1, [])\n",
    "        return self.res\n",
    "\n",
    "    def combination(self, k, target, start, res):\n",
    "        if len(res) == k and target == 0:\n",
    "            self.res.append(res)\n",
    "            return\n",
    "\n",
    "        if len(res) == k or target < 0:\n",
    "            return\n",
    "            \n",
    "        for i in range(start, 10):\n",
    "            self.combination(k, target-i, i+1, res+[i]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        @lru_cache(None)\n",
    "        def dfs(used, k, n, ci):\n",
    "            if k==0 and n==0:\n",
    "                return [[]]\n",
    "            elif k==0 or n==0:\n",
    "                return []\n",
    "            res = []\n",
    "            for i in range(ci, 10):\n",
    "                if 1<<i&used==0 and i<=n:\n",
    "                    ret = dfs(used|1<<i, k-1, n-i, i+1)\n",
    "                    for r in ret:\n",
    "                        res.append([i]+r)\n",
    "            return res\n",
    "        return dfs(0,k,n,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        @lru_cache(None)\n",
    "        def dfs(used, k, n, ci):\n",
    "            if k==0 and n==0:\n",
    "                return [[]]\n",
    "            elif k==0 or n==0:\n",
    "                return []\n",
    "            res = []\n",
    "            for i in range(ci, 10):\n",
    "                if 1<<i&used==0 and i<=n:\n",
    "                    ret = dfs(used|1<<i, k-1, n-i, i+1)\n",
    "                    for r in ret:\n",
    "                        res.append([i]+r)\n",
    "            return res\n",
    "        return dfs(0,k,n,1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        path = []\n",
    "\n",
    "        def backtrack(n, k, sum_, startIndex):\n",
    "            if sum_ > n: return\n",
    "            if len(path) == k:\n",
    "                if sum_ == n:\n",
    "                    res.append(path[:])\n",
    "                return\n",
    "                \n",
    "            \n",
    "            for i in range(startIndex, 10):\n",
    "                path.append(i)\n",
    "                sum_ += i\n",
    "                backtrack(n, k, sum_, i + 1)\n",
    "                sum_ -= i\n",
    "                path.pop()\n",
    "        \n",
    "        backtrack(n, k, 0, 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        def dfs(index,j,target):\n",
    "            if target==0 and index==k:\n",
    "                res.append(path.copy())\n",
    "            if target<0 or index>k:\n",
    "                return\n",
    "            for i in range(j,10):\n",
    "                path.append(i)\n",
    "                dfs(index+1,i+1,target-i)\n",
    "                path.pop()\n",
    "        res=[]\n",
    "        path=[]\n",
    "        dfs(0,1,n)\n",
    "        return res\n",
    "\n",
    "       \n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        res=[]\n",
    "        def dfs(k,n,nums,i):\n",
    "            if k==0 and n==0:\n",
    "                res.append(nums[:])\n",
    "                return\n",
    "            if k<=0 or n<=0 or i>9:return\n",
    "            nums.append(i)\n",
    "            dfs(k-1,n-i,nums,i+1)\n",
    "            nums.pop()\n",
    "            dfs(k,n,nums,i+1)\n",
    "        \n",
    "        dfs(k,n,[],1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def __init__(self):\n",
    "        self.sum = 0\n",
    "        self.result = []\n",
    "        self.path = []\n",
    "    def combinationSum3(self, k,n):\n",
    "        def backtracking(k,n,startidx):\n",
    "            if len(self.path) == k:\n",
    "                if self.sum == n:\n",
    "                # 所以在这里k就是树的深度，什么时候遍历到叶子节点，\n",
    "                # 也就是什么时候，选完了k个数，那就什么时候终止即可。\n",
    "                    self.result.append(self.path[:])\n",
    "                # 这里不能只是appendpath，而是应该append（path[:]）\n",
    "                # 在这里的话，一维数组path存放符合条件的结果\n",
    "                # 二维数组result存放最终的结果集\n",
    "                    return\n",
    "                else:\n",
    "                    return\n",
    "\n",
    "                # 这句代码\n",
    "\n",
    "            # for i in range(startidx,n + 1):\n",
    "            for i in range(startidx, 9 - (k - len(self.path)) + 2):\n",
    "                self.sum += i\n",
    "                # 也就是说明取不到 n - (k - len(path)) + 2 这个值\n",
    "                # 如果是剪枝操作的话，应该就是上面这层for循环的写法\n",
    "                # for循环用来遍历集合中的每一个元素\n",
    "                self.path.append(i)\n",
    "                # 在这里有append，下面就有pop，在回溯的代码模板中，for循环中的 处理过程和 回溯操作是一一对应的\n",
    "                backtracking(k,n,i + 1)\n",
    "                self.sum -= i\n",
    "                # 这就说明，下一层搜索要从i的后面，也就是i+1开始\n",
    "                self.path.pop()\n",
    "\n",
    "        backtracking(k,n,1)\n",
    "        return self.result\n",
    "\n",
    "            # last_startidx = n - (k - len(path)) + 1\n",
    "# n = 4\n",
    "# k = 2\n",
    "# print(Solution().combine(n,k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        path, res = [], []\n",
    "        def backstracking(startidx, endidx):\n",
    "            if len(path) == k and sum(path) == n:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            elif len(path) >= k:\n",
    "                return\n",
    "            print(len(path), startidx, endidx + 1 - (k - len(path)))\n",
    "            for i in range(startidx, endidx + 1 - (k - len(path))):\n",
    "                path.append(i)\n",
    "                backstracking(i + 1, 10)\n",
    "                path.pop()\n",
    "        backstracking(1, 10)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = []\n",
    "        self.path = []\n",
    "\n",
    "    def backtracking(self, startIndex, k, n, sums):\n",
    "        if sums > n:\n",
    "            return\n",
    "        if len(self.path) == k - 1:\n",
    "            if startIndex <= n - sum(self.path) < 10:\n",
    "                self.ans.append(self.path[:] + [n - sum(self.path)])\n",
    "            return\n",
    "        for i in range(startIndex, 11-(k-len(self.path))):\n",
    "            sums += i\n",
    "            self.path.append(i)\n",
    "            self.backtracking(i+1, k, n, sums)\n",
    "            self.path.pop()\n",
    "            sums -= i\n",
    "\n",
    "    def combinationSum3(self, k: int, n: int):\n",
    "        self.backtracking(1, k, n, 0)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "\n",
    "        def dfs(begin, size, k, target, path, res):\n",
    "            if len(path) == k:\n",
    "                if target == 0:\n",
    "                    res.append(path)\n",
    "                return\n",
    "            \n",
    "            for i in range(begin, size):\n",
    "                if target - i < 0:\n",
    "                    break\n",
    "                dfs(i + 1, size, k, target - i, path + [i], res)\n",
    "\n",
    "\n",
    "        path = []\n",
    "        res = []\n",
    "        dfs(1, 10, k, n, path, res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    k = 0\n",
    "    res = []\n",
    "    tmp = []\n",
    "    n = 0\n",
    "\n",
    "    def dfs(self, level):\n",
    "        if level == self.k: \n",
    "            if sum(self.tmp) == self.n:\n",
    "                self.res.append(self.tmp)\n",
    "            return\n",
    "        start = 1 if len(self.tmp) == 0 else self.tmp[-1]+1\n",
    "        for i in range(start, 10):\n",
    "            if i in self.tmp: continue\n",
    "            self.tmp.append(i)\n",
    "            self.dfs(level+1)\n",
    "            self.tmp = self.tmp[:-1]\n",
    "\n",
    "\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        self.k = k\n",
    "        self.n = n\n",
    "        self.res = []\n",
    "        self.tmp = []\n",
    "        self.dfs(0)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum3(self, k: int, n: int) -> List[List[int]]:\n",
    "        def backtrace(cur_sum, n, k, path, result, start):\n",
    "            if cur_sum > n:\n",
    "                return\n",
    "            if cur_sum == n:\n",
    "                if len(path[:]) == k:\n",
    "                    result.append(path[:])\n",
    "                    return\n",
    "            \n",
    "            for i in range(start, 10):\n",
    "                cur_sum += i\n",
    "                path.append(i)\n",
    "                # 因为不能有重复数字，这里是得从i+1之后的\n",
    "                backtrace(cur_sum, n, k, path, result, i+1)\n",
    "                cur_sum -= i    \n",
    "                path.pop()\n",
    "        \n",
    "\n",
    "        path = []\n",
    "        result = []\n",
    "        backtrace(0, n, k, path, result, 1)\n",
    "        return result\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        @functools.lru_cache(maxsize = None)#对于函数的注解\n",
    "        def combs(remain):\n",
    "            if remain == 0:\n",
    "                return 1\n",
    "            \n",
    "            result = 0\n",
    "            for num in nums:\n",
    "                if remain - num >= 0:\n",
    "                    result += combs(remain - num)\n",
    "                else:\n",
    "                    break\n",
    "            return result\n",
    "        \n",
    "        return combs(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # n = len(nums)\n",
    "        \n",
    "        f = [0] * (target+1)\n",
    "        f[0] = 1\n",
    "        \n",
    "        for i in range(1,target+1):\n",
    "            for j in nums:\n",
    "                if j<=i:\n",
    "                    f[i] += f[i-j]\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        mem = [int(0)  for i in range(target+1)]\n",
    "        mem[0] = 1\n",
    "        for i in range(1,target+1):\n",
    "            for j in nums:\n",
    "                if i >= j:\n",
    "                    mem[i] = mem[i] + mem[i-j]\n",
    "        return mem[target]\n",
    "                \n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums, target):\n",
    "        dp = [1]\n",
    "        nums.sort()\n",
    "        for i in range(1, target + 1):\n",
    "            dp.append(0)\n",
    "            for j in nums:\n",
    "                if j <= i:\n",
    "                    dp[-1] += dp[i - j]\n",
    "                else:\n",
    "                    break\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 动态规划法\n",
    "    def combinationSum4(self, nums, target):\n",
    "        dp = collections.defaultdict(int)\n",
    "        dp[0] = 1\n",
    "        for i in range(target + 1):\n",
    "            for num in nums:\n",
    "                if i - num >= 0:\n",
    "                    dp[i] += dp[i - num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        from collections import defaultdict\n",
    "        dp, nums = defaultdict(int), sorted(nums)\n",
    "        for num in nums:\n",
    "            dp[num] = 1\n",
    "        for loop in range(2, target + 1):\n",
    "            for num in nums:\n",
    "                dp[loop] += dp[loop - num]\n",
    "        return dp[target]            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #如果数组中没有元素，显然就不能组合成任何target\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "\n",
    "        self.dp=[-1]*(target+1)\n",
    "        self.dfs(nums,target)\n",
    "        # print(self.dp)\n",
    "        return self.dp[-1]\n",
    "\n",
    "    def dfs(self,nums,target):\n",
    "\n",
    "        if target==0:\n",
    "            return 1\n",
    "\n",
    "        if self.dp[target]!=-1:\n",
    "            return self.dp[target]\n",
    "\n",
    "        res=0\n",
    "        for i in range(0,len(nums)):\n",
    "            \n",
    "            if nums[i]<=target:\n",
    "                res+=self.dfs(nums,target-nums[i])\n",
    "\n",
    "        self.dp[target]=res         #存储结果\n",
    "        return res              #返回结果\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.me = []\n",
    "    def combinationSum4(self, nums: 'List[int]', target: 'int') -> 'int':\n",
    "        if not nums or target < 1:\n",
    "            return 0\n",
    "        self.me = [-1 for i in range(target+1)]\n",
    "        res = self.help(nums, target, [])\n",
    "        return res\n",
    "    def help(self, nums, target, ans):\n",
    "        if target == 0:\n",
    "            return 1\n",
    "        if self.me[target] != -1:\n",
    "            return self.me[target]\n",
    "        res = 0\n",
    "        for i in nums:\n",
    "            if i <= target:\n",
    "                res += self.help(nums, target-i, ans)\n",
    "        self.me[target] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        self.cache = {}\n",
    "        self.n = nums\n",
    "        return self.helper(target)\n",
    "    \n",
    "    def helper(self, target):\n",
    "        if target in self.cache:\n",
    "            return self.cache[target]\n",
    "        res = 0\n",
    "        for i in self.n:\n",
    "            if i > target:\n",
    "                break\n",
    "            elif i == target:\n",
    "                res += 1\n",
    "            else:\n",
    "                res += self.helper(target - i)\n",
    "        self.cache[target] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: 'List[int]', target: 'int') -> 'int':\n",
    "        \n",
    "        def comb_(nums, target, dp):\n",
    "            if dp[target] >= 0:\n",
    "                return dp[target]\n",
    "            c = 0\n",
    "            for i in nums:\n",
    "                if i > target:\n",
    "                    break\n",
    "                c += comb_(nums, target - i, dp)\n",
    "            dp[target] = c\n",
    "            return c\n",
    "        \n",
    "        dp = [-1] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        nums.sort()\n",
    "        return comb_(nums, target, dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        nums = sorted(nums)\n",
    "        cals = {}\n",
    "        def dfs(t):\n",
    "            ans = 0\n",
    "            if t == 0:\n",
    "                return 1\n",
    "            if t in cals:\n",
    "                return cals[t]\n",
    "            for n in nums:\n",
    "                if t-n < 0:\n",
    "                    break\n",
    "                ans += dfs(t-n)\n",
    "            cals[t] = ans\n",
    "            return ans\n",
    "        return dfs(target)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\r\n",
    "        if len(nums) == 0: return 0\r\n",
    "        dp = [0] * (target + 1)\r\n",
    "        dp[0] = 1\r\n",
    "        for x in range(1, target + 1):\r\n",
    "            for num in nums:\r\n",
    "                if x - num >= 0:\r\n",
    "                    dp[x] += dp[x-num]\r\n",
    "        return dp[target]\r\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        size = len(nums)\n",
    "        if size == 0 or target <= 0:\n",
    "            return 0\n",
    "\n",
    "        dp = [0 for _ in range(target + 1)]\n",
    "        \n",
    "        # 这一步很关键，想想为什么 dp[0] 是 1\n",
    "        # 因为 0 表示空集，空集和它\"前面\"的元素凑成一种解法，所以是 1\n",
    "        # 这一步要加深体会\n",
    "        \n",
    "        dp[0] = 1\n",
    "\n",
    "        for i in range(1, target + 1):\n",
    "            for j in range(size):\n",
    "                if i >= nums[j]:\n",
    "                    dp[i] += dp[i - nums[j]]\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from copy import deepcopy\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        size = len(nums)\n",
    "        if size == 0 or target <= 0:\n",
    "            return 0\n",
    "\n",
    "        dp = [0 for _ in range(target + 1)]\n",
    "        \n",
    "        # 这一步很关键，想想为什么 dp[0] 是 1\n",
    "        # 因为 0 表示空集，空集和它\"前面\"的元素凑成一种解法，所以是 1\n",
    "        # 这一步要加深体会\n",
    "        \n",
    "        dp[0] = 1\n",
    "\n",
    "        for i in range(1, target + 1):\n",
    "            for j in range(size):\n",
    "                if i >= nums[j]:\n",
    "                    dp[i] += dp[i - nums[j]]\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        # import functools\n",
    "\n",
    "        # @functools.lru_cache(None)\n",
    "        # def back(tmp):\n",
    "        #     if tmp==target:\n",
    "        #         return 1\n",
    "        #     ans=0\n",
    "        #     for i in range(len(nums)):\n",
    "        #         val=tmp+nums[i]\n",
    "        #         if val>target:continue\n",
    "        #         ans+=back(val)\n",
    "        #     return ans\n",
    "\n",
    "        # return back(0)\n",
    "\n",
    "        dp=[0]*(target+1)\n",
    "        dp[0]=1\n",
    "        for i in range(1,target+1):\n",
    "            for j in range(len(nums)):\n",
    "                if i>=nums[j]:\n",
    "                    dp[i]+=dp[i-nums[j]]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    count = []\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0 for i in range(target + 1)]\n",
    "        dp[0] = 1\n",
    "        for t in range(target + 1):\n",
    "            for n in nums:        \n",
    "                if n <= t:\n",
    "                    dp[t] += dp[t - n]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    dp[i] += dp[i-num]\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        size = len(nums)\n",
    "        if size == 0 or target <= 0:\n",
    "            return 0\n",
    "\n",
    "        dp = [0 for _ in range(target + 1)]\n",
    "        \n",
    "        # 这一步很关键，想想为什么 dp[0] 是 1\n",
    "        # 因为 0 表示空集，空集和它\"前面\"的元素凑成一种解法，所以是 1\n",
    "        # 这个值被其它状态参考，设置为 1 是合理的\n",
    "        \n",
    "        dp[0] = 1\n",
    "\n",
    "        for i in range(1, target + 1):\n",
    "            for j in range(size):\n",
    "                if i >= nums[j]:\n",
    "                    dp[i] += dp[i - nums[j]]\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        from collections import defaultdict\n",
    "        if not nums:\n",
    "            return 0\n",
    "        dp = defaultdict(int)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1):\n",
    "            res = 0\n",
    "            for num in nums:\n",
    "                if i >= num:\n",
    "                    res += dp[i - num]\n",
    "            dp[i] = res\n",
    "        \n",
    "        # print(dp)\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        #回溯算法(超出内存限制)\n",
    "        # result = []\n",
    "        # def helper(tmp):\n",
    "        #     if sum(tmp) == target:\n",
    "        #         result.append(tmp)\n",
    "        #         return\n",
    "        #     if sum(tmp) > target:\n",
    "        #         return\n",
    "        #     for i in range(len(nums)):\n",
    "        #         tmp.append(nums[i])\n",
    "        #         helper(tmp[:])\n",
    "        #         tmp.pop()\n",
    "        # helper([])\n",
    "        # return len(result)\n",
    "\n",
    "        #因为返回的是数量，所以可以用动态规划求解\n",
    "        dp = [0]*(target+1)\n",
    "\n",
    "        dp[0] = 1\n",
    "        for i in range(1,target+1):\n",
    "            for num in nums:\n",
    "                if i - num < 0:\n",
    "                    continue\n",
    "                dp[i] += dp[i-num]\n",
    "        print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0 for _ in range(target + 1)]\n",
    "        dp[0] = 1\n",
    "        for j in range(target + 1):\n",
    "            for i in range(len(nums)):\n",
    "                if j >= nums[i]: dp[j] += dp[j - nums[i]]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp=[0]*(target+1)\n",
    "        dp[0] =1\n",
    "        for j in range(target+1):\n",
    "            for num in nums:\n",
    "                if num <=j:\n",
    "                    dp[j] = dp[j]+dp[j-num]\n",
    "        return dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [1] + [0] * target\n",
    "        for v in range(1, target+1):\n",
    "            for num in nums:\n",
    "                if num <= v:\n",
    "                    dp[v] += dp[v-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\r\n",
    "        dp = [1] + [0] * target\r\n",
    "        for i in range(1, target + 1):\r\n",
    "            for num in nums:\r\n",
    "                if num <= i:\r\n",
    "                    dp[i] += dp[i - num]\r\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "\n",
    "        def dp(target):\n",
    "            if target == 0:\n",
    "                return 1\n",
    "            if target < 0:\n",
    "                return 0\n",
    "\n",
    "            total = 0\n",
    "            for n in nums:\n",
    "                total += dp(target-n)\n",
    "\n",
    "            return total\n",
    "        return dp(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * (target+1)\n",
    "        dp[0] = 1\n",
    "        for j in range(target+1):\n",
    "            for num in nums:\n",
    "                if j >= num:\n",
    "                    dp[j] += dp[j-num]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        # dp = [0]*(target+1)\n",
    "        # dp[0] = 1\n",
    "        # for i in range(target+1):\n",
    "        #     for num in nums:\n",
    "        #         if i>=num:\n",
    "        #             dp[i]+=dp[i-num]\n",
    "        # return dp[-1]\n",
    "        n=len(nums)\n",
    "        dp=[0]*(target+1)\n",
    "        dp[0]=1\n",
    "        for i in range(target+1):\n",
    "            for num in nums:\n",
    "                if i>=num:\n",
    "                    dp[i]+=dp[i-num]\n",
    "            \n",
    "        return dp[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "\n",
    "        #dp[i] 综合为i的元素组合的个数\n",
    "\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, target + 1):\n",
    "            for j in range(0, len(nums)):\n",
    "                if i >= nums[j]:\n",
    "                    dp[i] += dp[i - nums[j]]\n",
    "        return dp[-1]\n",
    "        \n",
    "        # for i in range(1, len(nums)):\n",
    "        #     for j in range(nums[i], target + 1):\n",
    "        #         dp[j] += dp[j - nums[i]] * dp[nums[i]]\n",
    "        #     print(dp)\n",
    "        # return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        # 定义状态，dp[i] 组合总和为 i 时组合的个数，因为可以取到target，所以长度为target+1，初始化dp[0]=1或全为1\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        \n",
    "        for i in range(1, target + 1):\n",
    "            for num in nums:\n",
    "                if num <= i:\n",
    "                    dp[i] += dp[i-num]\n",
    "        return dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def f(i: int):\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            return sum(f(i - n) for n in nums if i - n >= 0)\n",
    "\n",
    "        return f(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        \n",
    "        res = set()\n",
    "        \n",
    "        def opt(i, comb, val):\n",
    "            if val == target:\n",
    "                res.add(tuple(comb))\n",
    "            elif val < target:\n",
    "                if i < len(candidates) - 1:\n",
    "                    opt(i + 1, comb, val)\n",
    "                comb.append(candidates[i])\n",
    "                opt(i, comb, val + candidates[i])\n",
    "                comb.pop()\n",
    "        \n",
    "        opt(0, [], 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dfs(l,r,num,target,ans,lastans):\n",
    "    if target < 0 or l == r:return\n",
    "    if target ==0:\n",
    "        lastans.append(ans)\n",
    "        return \n",
    "    for i in range(l,r):\n",
    "        dfs(i,r,num,target-num[i],ans+[num[i]],lastans)\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, num: 'List[int]', target: 'int') -> 'List[List[int]]':\n",
    "        num.sort()\n",
    "        lastans =  []\n",
    "        dfs(0,len(num),num,target,[],lastans)\n",
    "        return lastans\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates, target):\n",
    "        result = []\n",
    "        candidates.sort()\n",
    "\n",
    "        def dfs(target, index, path):\n",
    "            if target < 0:\n",
    "                return\n",
    "            if target == 0:\n",
    "                result.append(path)\n",
    "\n",
    "            for i in range(index, len(candidates)):\n",
    "                if candidates[i] > target: break #这句话很关键，可以大大减少Runtime\n",
    "                dfs(target-candidates[i], i, path+[candidates[i]])\n",
    "\n",
    "        dfs(target, 0, [])\n",
    "\n",
    "        return result\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def combinationSum(self, candidates, target):\n",
    "        from collections import deque\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        candidates.sort()\n",
    "        result = []\n",
    "        stack = deque()\n",
    "        n = len(candidates)\n",
    "        for i in range(n):\n",
    "            if candidates[i] == target:\n",
    "                result.append([candidates[i]])\n",
    "            else:\n",
    "                stack.append([candidates[i]])\n",
    "        def add_element(stack):\n",
    "            n = len(stack)\n",
    "            if n == 0:\n",
    "                return\n",
    "            for _ in range(n):\n",
    "                arr = stack.pop()\n",
    "                for c in candidates:\n",
    "                    if c >= arr[-1]:\n",
    "                        new_arr = arr + [c]\n",
    "                        if sum(new_arr) == target:\n",
    "                            result.append(new_arr)\n",
    "                        if sum(new_arr) > target:\n",
    "                            break\n",
    "                        stack.appendleft(new_arr)\n",
    "            add_element(stack)\n",
    "        \n",
    "        add_element(stack)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, nums: 'List[int]', t: 'int') -> 'List[List[int]]':\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        for i in range(0,t+1):ans.append([])\n",
    "        ans[0].append([])\n",
    "        for i in nums:\n",
    "            for j in range(i,t+1):\n",
    "                for k in ans[j-i]:\n",
    "                    ans[j].append(k + [i])\n",
    "        ans[-1].sort()\n",
    "        i = 0\n",
    "        while i+1 < len(ans[-1]):\n",
    "            if(ans[-1][i]==ans[-1][i+1]):del ans[-1][i+1]\n",
    "            else:i+=1\n",
    "        return ans[-1]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.ans = []\n",
    "        self.f(target,candidates,[])\n",
    "        return self.ans\n",
    "        \n",
    "    def f(self,target,nums,pre):\n",
    "        if target < 0 or not nums:\n",
    "            return\n",
    "        if target == 0:\n",
    "            self.ans.append(pre)\n",
    "            return\n",
    "        self.f(target-nums[0],nums,pre+[nums[0]])\n",
    "        self.f(target,nums[1:],pre)\n",
    "        return\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates, target):\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        candidates.sort()\n",
    "        if target < candidates[0]:\n",
    "            return []\n",
    "        _dict = {}\n",
    "        pos = 0\n",
    "        len_c = len(candidates)\n",
    "        for cur in range(candidates[0], target + 1):\n",
    "            if pos < len_c and cur == candidates[pos]:\n",
    "                tmp = [[candidates[pos]]]\n",
    "                pos += 1\n",
    "            else:\n",
    "                tmp = []\n",
    "            for a in range(candidates[0], min(cur - candidates[0] , (cur + candidates[0]) // 2) + 1):\n",
    "                b = cur - a\n",
    "                tmp += [sorted(i + j) for i in _dict[a] for j in _dict[b]]\n",
    "            \n",
    "            TMP = []\n",
    "            for t in tmp:\n",
    "                if not t in TMP:\n",
    "                    TMP.append(t)\n",
    "            _dict[cur] = TMP\n",
    "            \n",
    "        return _dict[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates, target):\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        candidates.sort()\n",
    "        if target < candidates[0]:\n",
    "            return []\n",
    "        _dict = {}\n",
    "        pos = 0\n",
    "        len_c = len(candidates)\n",
    "        for cur in range(candidates[0], target + 1):\n",
    "            if pos < len_c and cur == candidates[pos]:\n",
    "                tmp = [[candidates[pos]]]\n",
    "                pos += 1\n",
    "            else:\n",
    "                tmp = []\n",
    "            for a in range(candidates[0], cur - candidates[0] + 1):\n",
    "                b = cur - a\n",
    "                tmp += [sorted(i + j) for i in _dict[a] for j in _dict[b]]\n",
    "            \n",
    "            TMP = []\n",
    "            for t in tmp:\n",
    "                if not t in TMP:\n",
    "                    TMP.append(t)\n",
    "            _dict[cur] = TMP\n",
    "            \n",
    "        return _dict[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates, target):\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        l = len(candidates)\n",
    "        res0, sum0 = [[0] * l], [0]\n",
    "        res1, sum1 = [], []\n",
    "        ans = []\n",
    "        while res0:\n",
    "            for i in range(len(res0)):\n",
    "                for j in range(l):\n",
    "                    res = res0[i].copy()\n",
    "                    _sum = sum0[i] + candidates[j]\n",
    "                    res[j] += 1\n",
    "                    if res not in ans and res not in res1:\n",
    "                        if _sum == target:\n",
    "                            ans.append(res)\n",
    "                        elif _sum < target:\n",
    "                            res1.append(res)\n",
    "                            sum1.append(_sum)\n",
    "            res0, sum0 = res1, sum1\n",
    "            res1, sum1 = [], []\n",
    "        for i, a in enumerate(ans):\n",
    "            ans[i] = []\n",
    "            for j in range(l):\n",
    "                ans[i] += [candidates[j]] * a[j]\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates, target):\n",
    "        ret=[]\n",
    "        # 以candidates各元素为起点向后搜索\n",
    "        candidates.sort()\n",
    "        for indStart in range(len(candidates)):\n",
    "            List=[[candidates[indStart]]]\n",
    "            IndRight=[indStart]\n",
    "            SumList=[candidates[indStart]]\n",
    "            ListNext=[]\n",
    "            IndRightNext=[]\n",
    "            SumListNext=[]\n",
    "            while(len(List)!=0):\n",
    "                for i in range(len(List)):\n",
    "                    if(SumList[i]<target):# 继续向右探索\n",
    "                        for j in list(range(len(candidates)))[IndRight[i]:]:\n",
    "                            ListNext.append(List[i]+[candidates[j]])\n",
    "                            IndRightNext.append(j)\n",
    "                            SumListNext.append(SumList[i]+candidates[j])\n",
    "                    else:# 终止探索\n",
    "                        if(SumList[i]==target):\n",
    "                            ret.append(List[i])\n",
    "                List=ListNext\n",
    "                IndRight=IndRightNext\n",
    "                SumList=SumListNext\n",
    "                ListNext=[]\n",
    "                IndRightNext=[]\n",
    "                SumListNext=[]\n",
    "                \n",
    "        return ret          \n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates, target):\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        self.res = []\n",
    "        candidates.sort()\n",
    "        self.dfs(candidates, target ,0,[])\n",
    "        return self.res\n",
    "    def dfs(self, candidates, target,start,answer):\n",
    "        if target == 0:\n",
    "            self.res.append(answer[:])\n",
    "            return\n",
    "        if target < 0:\n",
    "            return\n",
    "        for i in range(start,len(candidates)):\n",
    "            print(i)\n",
    "            if candidates[i] > target:\n",
    "                break\n",
    "            answer.append(candidates[i])\n",
    "            self.dfs(candidates, target - candidates[i],i,answer)\n",
    "            answer.pop()\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def operat(self,candidates:'List[int]',target:'int',prex:'List[int]', res:'List[List[int]]'):\n",
    "        if target==0:\n",
    "            prex.sort()\n",
    "            res.append(prex)\n",
    "            return\n",
    "        elif target<candidates[0]:\n",
    "            return\n",
    "        else:\n",
    "            for num in candidates:\n",
    "                a=[]\n",
    "                a[:]=prex\n",
    "                a.append(num)\n",
    "                self.operat(candidates,target-num,a,res)\n",
    "        \n",
    "            \n",
    "        \n",
    "    def combinationSum(self, candidates: 'List[int]', target: 'int') -> 'List[List[int]]':\n",
    "        candidates.sort()\n",
    "        res=[]\n",
    "        for num in candidates:\n",
    "            self.operat(candidates,target-num,[num],res)\n",
    "        \n",
    "        out=[]\n",
    "        for nums in res:\n",
    "            if nums not in out:\n",
    "                out.append(nums)\n",
    "        return out\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def operat(self,candidates:'List[int]',target:'int',prex:'List[int]', res:'List[List[int]]'):\n",
    "        if target==0:\n",
    "            prex.sort()\n",
    "            res.append(prex)\n",
    "            return\n",
    "        elif target<candidates[0]:\n",
    "            return\n",
    "        else:\n",
    "            for num in candidates:\n",
    "                a=[]\n",
    "                a[:]=prex\n",
    "                a.append(num)\n",
    "                self.operat(candidates,target-num,a,res)\n",
    "        \n",
    "            \n",
    "        \n",
    "    def combinationSum(self, candidates: 'List[int]', target: 'int') -> 'List[List[int]]':\n",
    "        candidates.sort()\n",
    "        res=[]\n",
    "        for num in candidates:\n",
    "            self.operat(candidates,target-num,[num],res)\n",
    "        \n",
    "        out=[]\n",
    "        for nums in res:\n",
    "            if nums not in out:\n",
    "                out.append(nums)\n",
    "        return out\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates, target):\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        \n",
    "        if len(candidates) == 0:\n",
    "            return[]\n",
    "        res = []\n",
    "        cur = self.check(candidates, target)\n",
    "        final = self.undul(cur)\n",
    "        return final\n",
    "                    \n",
    "                    \n",
    "        \n",
    "    def check(self, candidates, target):\n",
    "        out = []\n",
    "        if target == 0:\n",
    "            return [[]]\n",
    "        for i, v in enumerate(candidates):\n",
    "            if target >= v:\n",
    "                cur_out = self.check(candidates, target-v)\n",
    "                for o in cur_out:\n",
    "                    out.append([v]+o)\n",
    "        return out\n",
    "    \n",
    "    def undul(self, nums):\n",
    "        used = []\n",
    "        for l in nums:\n",
    "            l.sort()\n",
    "            if l in used:\n",
    "                continue\n",
    "            else:\n",
    "                used.append(l)\n",
    "        return used\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates, target):\n",
    "        \"\"\"\n",
    "        :type candidates: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        self.ret = []\n",
    "        def f(prev, target):\n",
    "            # print(prev, target)\n",
    "            if target == 0:\n",
    "                self.ret.append(sorted(prev[:]))\n",
    "                return \n",
    "            for i in candidates:\n",
    "                if target >= i:\n",
    "                    f(prev[:] + [i], target - i)\n",
    "            return\n",
    "        \n",
    "        f([], target)\n",
    "        \n",
    "        self.ret = [tuple(i) for i in self.ret]\n",
    "        self.ret = set(self.ret)\n",
    "        return [list(i) for i in self.ret]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digui(self,sumpath,path,target,candidates):\n",
    "        if target<0:\n",
    "            return\n",
    "        if target==0:\n",
    "            sumpath.append(path[:])\n",
    "            return \n",
    "        for i in candidates:\n",
    "            path.append(i)\n",
    "            self.digui(sumpath,path,target-i,candidates)\n",
    "            path.remove(i)\n",
    "    def combinationSum(self, candidates: 'List[int]', target: 'int') -> 'List[List[int]]':\n",
    "        sumpath=[]\n",
    "        path=[]\n",
    "        self.digui(sumpath,path,target,candidates)\n",
    "        sumpath=list(set(map(tuple,map(sorted,sumpath))))\n",
    "        print(sumpath)\n",
    "        sumpath.reverse()\n",
    "        print(sumpath)\n",
    "        return sumpath"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.combos = []\n",
    "        self.backtrack(candidates, target, [], len(candidates), 0)\n",
    "        return self.combos\n",
    "\n",
    "    def backtrack(self, candidates, target, path, cand_len, prev):\n",
    "        if target < 0:\n",
    "            return\n",
    "        if target == 0:\n",
    "            self.combos.append(path)\n",
    "            return\n",
    "        for i in range(cand_len):\n",
    "            if candidates[i] >= prev:\n",
    "                self.backtrack(candidates, target-candidates[i], path + [candidates[i]], cand_len, candidates[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        size = len(candidates)\n",
    "        if size == 0:\n",
    "            return []\n",
    "\n",
    "        # 剪枝的前提是数组元素排序\n",
    "        # 深度深的边不能比深度浅的边还小\n",
    "        # 要排序的理由：1、前面用过的数后面不能再用；2、下一层边上的数不能小于上一层边上的数。\n",
    "        candidates.sort()\n",
    "        # 在遍历的过程中记录路径，一般而言它是一个栈\n",
    "        path = []\n",
    "        res = []\n",
    "        # 注意要传入 size ，在 range 中， size 取不到\n",
    "        self.__dfs(candidates, 0, size, path, res, target)\n",
    "        return res\n",
    "\n",
    "    def __dfs(self, candidates, begin, size, path, res, target):\n",
    "        # 先写递归终止的情况\n",
    "        if target == 0:\n",
    "            # Python 中可变对象是引用传递，因此需要将当前 path 里的值拷贝出来\n",
    "            # 或者使用 path.copy()\n",
    "            res.append(path[:])\n",
    "\n",
    "        for index in range(begin, size):\n",
    "            residue = target - candidates[index]\n",
    "            # “剪枝”操作，不必递归到下一层，并且后面的分支也不必执行\n",
    "            if residue < 0:\n",
    "                break\n",
    "            path.append(candidates[index])\n",
    "            # 因为下一层不能比上一层还小，起始索引还从 index 开始\n",
    "            self.__dfs(candidates, index, size, path, res, residue)\n",
    "            path.pop()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        \n",
    "    def __combination(self, candidates, index, target, res):\n",
    "        if target == 0:\n",
    "            self.res.append(list(res))\n",
    "            return \n",
    "        if target < 0 or index >= len(candidates):\n",
    "            return \n",
    "        \n",
    "        for i in range(index, len(candidates)):\n",
    "            res.append(candidates[i])\n",
    "            self.__combination(candidates, i, target-candidates[i], res)\n",
    "            res.pop()\n",
    "         \n",
    "    def combinationSum(self, candidates: list, target: int) -> list:\n",
    "        unique_candidates = set(candidates)\n",
    "        candidates = list(unique_candidates)\n",
    "        candidates.sort()\n",
    "        res = []\n",
    "        self.__combination(candidates, 0, target, res)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        length = len(candidates)\n",
    "        candidates.sort() #便于剪枝\n",
    "\n",
    "        res = []\n",
    "        tmp = []\n",
    "\n",
    "        def dfs( x, sum, tmp ):\n",
    "            if sum == target:\n",
    "                res.append(tmp) #tmp是个对象， 当搜索过程中的tmp变了， res就随之改变\n",
    "                return\n",
    "            if sum > target or x == length:\n",
    "                return\n",
    "\n",
    "            for i in range(x, length):\n",
    "                c = candidates[i]\n",
    "                # sum += c\n",
    "                if sum + candidates[i] > target:\n",
    "                    break\n",
    "                # tmp .append(c) #不能用append会改变tmp对象\n",
    "                dfs( i, sum + c, tmp + [c]  )\n",
    "                # dfs( i, sum + candidates[i], tmp + [candidates[i]] )\n",
    "                # sum -= c\n",
    "                # tmp.pop()\n",
    "\n",
    "        dfs(0, 0, [] )\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        size = len(candidates)\n",
    "        if size == 0: return []\n",
    "\n",
    "        candidates.sort()  # 排序是为了剪枝\n",
    "        path = []  # 遍历时纪录路径\n",
    "        res = []\n",
    "        self.dfs(candidates, 0, size, path, res, target)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, candidates, begin, size, path, res, target):\n",
    "        if target == 0:  # target=0了，及递归终止\n",
    "            res.append(path[:])\n",
    "            return \n",
    "        for i in range(begin, size):\n",
    "            residue = target - candidates[i]\n",
    "            if residue < 0:  # 此数大于target，不用考虑，而且已经排序，后面的数也不考虑\n",
    "                break\n",
    "            path.append(candidates[i])\n",
    "            self.dfs(candidates, i, size, path, res, residue)  # 从当前i开始，防止重复解\n",
    "            path.pop()\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def huisu(candidates,target,res,mid,index):\n",
    "    if index==len(candidates):\n",
    "        return \n",
    "    if target==0:\n",
    "        res.append(mid.copy())\n",
    "        return\n",
    "\n",
    "    huisu(candidates,target,res,mid,index+1)\n",
    "\n",
    "    if (target - candidates[index] >= 0):\n",
    "        mid.append(candidates[index])\n",
    "        huisu(candidates,target-candidates[index],res,mid,index)\n",
    "        mid.pop()\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        res = []\n",
    "        mid = []\n",
    "\n",
    "        huisu(candidates,target,res,mid,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    组合 剪枝\n",
    "    1.数字排序\n",
    "    2.当后面的数字大于 target 直接 return\n",
    "    \"\"\"\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        candidates.sort()\n",
    "        self.combination(candidates, target, 0, [])\n",
    "        return self.res\n",
    "\n",
    "    def combination(self, candidate, target, start, res):\n",
    "        if target == 0:\n",
    "            self.res.append(res)\n",
    "            return\n",
    "\n",
    "        for i in range(start, len(candidate)):\n",
    "            e = candidate[i]\n",
    "            # 因为排序了，所以当 e > 大于 target 后面的数字肯定也不满足。直接 return\n",
    "            if e > target:\n",
    "                return\n",
    "            self.combination(candidate, target - e, i, res + [e])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        candidates = sorted(candidates)\n",
    "        def find(ind, res, gap):\n",
    "            for i in range(ind, len(candidates)):\n",
    "                num = candidates[i]\n",
    "                if num == gap:\n",
    "                    ans.append(res + [num])\n",
    "                elif num > gap:                    \n",
    "                    break\n",
    "                else:                    \n",
    "                    find(i, res+[num], gap-num)\n",
    "        find(0, [], target)\n",
    "        return ans\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        result = list()\n",
    "        def _visit(path, start_index):\n",
    "            sum_path = sum(path)\n",
    "            if sum_path == target:\n",
    "                result.append(path.copy())\n",
    "            elif sum_path > target:\n",
    "                return\n",
    "            for index, value in enumerate(candidates):\n",
    "                if index < start_index:\n",
    "                    continue\n",
    "                path.append(value)\n",
    "                _visit(path, index)\n",
    "                path.pop(-1)\n",
    "        candidates.sort()\n",
    "        _visit([], 0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        temp = set(candidates)\n",
    "        for c in candidates:\n",
    "            if(c > target):\n",
    "                temp.remove(c)\n",
    "        candidates = list(temp)\n",
    "        self.table = [[] for _ in range(target+1)]\n",
    "\n",
    "        for c in candidates:\n",
    "            self.table[c].append([c])\n",
    "\n",
    "        for i in range(1, target+1):\n",
    "            for j in range(len(candidates)):\n",
    "                k = i - candidates[j]\n",
    "                if(k > 0 and len(self.table[k]) > 0):\n",
    "                    for a in self.table[candidates[j]]:\n",
    "                        for b in self.table[k]:\n",
    "                            temp = sorted(a + b)\n",
    "                            if(temp not in self.table[i]):\n",
    "                                self.table[i].append(temp)\n",
    "\n",
    "        # print(self.table)\n",
    "        return self.table[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        res_dict = []\n",
    "        tdict_ = {}\n",
    "        for i in candidates:\n",
    "            tdict_[i] = 0\n",
    "        def sum(nums):\n",
    "            sums = 0\n",
    "            for i in nums:\n",
    "                sums += i\n",
    "            return sums\n",
    "\n",
    "        def backtrack(track, tdict):\n",
    "            if sum(track) == target:\n",
    "                if tdict not in res_dict:\n",
    "                    res.append(track[:])\n",
    "                    res_dict.append({key: value for key, value in tdict.items()})\n",
    "                return\n",
    "            if sum(track) > target:\n",
    "                return\n",
    "\n",
    "            for i in candidates:\n",
    "                track.append(i)\n",
    "                tdict[i] += 1\n",
    "                backtrack(track, tdict)\n",
    "                track.pop()\n",
    "                tdict[i] -= 1\n",
    "        backtrack([], tdict_)       \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def solve(candidates, target, index, curr, res):\n",
    "            if target == 0:\n",
    "                res.append(curr[:])\n",
    "                return\n",
    "            for i in range(index, len(candidates)):\n",
    "                if candidates[i] > target:\n",
    "                    break\n",
    "                curr.append(candidates[i])\n",
    "                solve(candidates, target-candidates[i], i, curr, res)\n",
    "                curr.pop()\n",
    "        curr = []\n",
    "        res = []\n",
    "        candidates.sort()\n",
    "        solve(candidates, target, 0, curr, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    item = []\n",
    "    res = []\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.item = []\n",
    "        self.res = []\n",
    "        candidates.sort()\n",
    "\n",
    "        self.search(0, candidates, target)\n",
    "        return self.res\n",
    "    \n",
    "    def search(self, start, nums, target):\n",
    "        if sum(self.item) > target:\n",
    "            return \n",
    "        \n",
    "        if sum(self.item) == target:\n",
    "            self.res.append(list(self.item))\n",
    "            return \n",
    "\n",
    "        for i in range(start, len(nums)):\n",
    "            if i > start and nums[i] == nums[i - 1]:\n",
    "                continue\n",
    "            self.item.append(nums[i])\n",
    "            self.search(i, nums, target)\n",
    "            self.item.pop()\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "     \n",
    "        self.res=[]\n",
    "        self.path=[]\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        sum_=0\n",
    "        self.backtracking(candidates,target,0,sum_)\n",
    "        return self.res\n",
    "    \n",
    "    def backtracking(self,candidates,target,start,sum_):\n",
    "        if sum_>target:\n",
    "            return\n",
    "  \n",
    "        if target==sum_:\n",
    "            self.res.append(self.path[:])\n",
    "            return\n",
    "        for i in range(start,len(candidates)):\n",
    "           \n",
    "            sum_+=candidates[i]\n",
    "            self.path.append(candidates[i])\n",
    "            self.backtracking(candidates,target,i,sum_)\n",
    "            sum_-=candidates[i]\n",
    "            self.path.pop()\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\r\n",
    "        def backtrack(candidates, target, begin, end):\r\n",
    "            if target == 0:\r\n",
    "                res.append(tmp.copy())\r\n",
    "                return\r\n",
    "            elif target < 0:\r\n",
    "                return\r\n",
    "            else:\r\n",
    "                for index in range(begin, end):\r\n",
    "                    tmp.append(candidates[index])\r\n",
    "                    backtrack(candidates, target - candidates[index], index, n)\r\n",
    "                    tmp.pop()\r\n",
    "\r\n",
    "        candidates.sort()   \r\n",
    "        n = len(candidates)\r\n",
    "        if n == 0:\r\n",
    "            return []     \r\n",
    "        res = []\r\n",
    "        tmp = []\r\n",
    "        backtrack(candidates, target, 0, n)\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\r\n",
    "        def backtrack(candidates, target, begin, end):\r\n",
    "            if target == 0:\r\n",
    "                res.append(tmp.copy())\r\n",
    "                return\r\n",
    "            elif target < 0:\r\n",
    "                return\r\n",
    "            else:\r\n",
    "                for index in range(begin, end):\r\n",
    "                    tmp.append(candidates[index])\r\n",
    "                    backtrack(candidates, target - candidates[index], index, n)\r\n",
    "                    tmp.pop()\r\n",
    "\r\n",
    "        candidates.sort()   \r\n",
    "        n = len(candidates)\r\n",
    "        if n == 0:\r\n",
    "            return []     \r\n",
    "        res = []\r\n",
    "        tmp = []\r\n",
    "        backtrack(candidates, target, 0, n)\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        self.res = []\n",
    "        def dfs(cur_sum,cur_cans,i):\n",
    "            print(cur_sum)\n",
    "            print(cur_cans)\n",
    "            print(i)\n",
    "            print(\"-----\")\n",
    "            if cur_sum > target:\n",
    "                return \n",
    "            elif cur_sum == target:\n",
    "                self.res.append(cur_cans)\n",
    "                return\n",
    "            else:\n",
    "\n",
    "                for j in range(i,len(candidates)):\n",
    "                    dfs(cur_sum+candidates[j],cur_cans+[candidates[j]],j)\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "        dfs(0,[],0)\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backtracking(self,candidates,path,result,index,sum,target):\n",
    "        if sum==target:\n",
    "            result.append(path[:])\n",
    "            return\n",
    "        if sum>target:\n",
    "            return\n",
    "        \n",
    "        for i in range(index,len(candidates)):\n",
    "            path.append(candidates[i])\n",
    "            sum+=candidates[i]\n",
    "            self.backtracking(candidates,path,result,i,sum,target)\n",
    "            sum-=candidates[i]\n",
    "            path.pop()\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        result=[]\n",
    "        self.backtracking(candidates,[],result,0,0,target)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def backtrace(path,start):\n",
    "            if sum(path) == target:\n",
    "                result.append(path.copy())\n",
    "                return\n",
    "\n",
    "            if sum(path) > target:\n",
    "                return\n",
    "\n",
    "            for i in range(start, len(candidates)):\n",
    "                    path.append(candidates[i])\n",
    "                    backtrace(path,i)\n",
    "                    path.pop()\n",
    "\n",
    "        result = []\n",
    "        backtrace([],0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        def backtrace(target, cur_sum, path, result, start):\n",
    "            if cur_sum > target:\n",
    "                return\n",
    "            if cur_sum == target:\n",
    "                result.append(path[:])\n",
    "                return\n",
    "\n",
    "            for i in range(start, len(candidates)):\n",
    "                cur_sum += candidates[i]\n",
    "                path.append(candidates[i])\n",
    "                backtrace(target, cur_sum, path, result, i)\n",
    "                cur_sum -= candidates[i]\n",
    "                path.pop()\n",
    "\n",
    "        \n",
    "        path = []\n",
    "        result = []\n",
    "        backtrace(target, 0, path, result, 0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:\n",
    "        res, n = [], len(candidates)\n",
    "\n",
    "        def func(temp, start):\n",
    "            sum_ = sum(temp)\n",
    "\n",
    "            if sum_ == target:\n",
    "                res.append(temp)\n",
    "                return \n",
    "            \n",
    "            if sum_ > target:\n",
    "                return \n",
    "            \n",
    "            for i in range(start, n):\n",
    "                func(temp+[candidates[i]], i)\n",
    "            \n",
    "        \n",
    "        func([], 0)\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
